class Solution {
    
private:
    int search(vector<vector<int>>& matrix,int** matrix_label,
    int i,int j)
    {
        if(matrix_label[i][j]!=0)
        {
            return matrix_label[i][j];
        }
        int max=0;
        int temp;
        static int direction[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
        for(int d=0;d<4;++d)
        {
            if(i+direction[d][0]>=0&&i+direction[d][0]<matrix.size()
            &&j+direction[d][1]>=0&&j+direction[d][1]<matrix[i].size()
            &&matrix[i+direction[d][0]][j+direction[d][1]]>matrix[i][j])
            {
                temp=search(matrix,matrix_label,i+direction[d][0],j+direction[d][1]);
                if(temp>max)
                {
                    max=temp;
                }
            }
        }
        matrix_label[i][j]=max+1;;
        return max+1;
    }
    
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int max=0;
        if(matrix.size()==0)
        {
            return 0;
        }
        int **matrix_label=new int*[matrix.size()];
        for(int i=0;i<matrix.size();++i)
        {
            matrix_label[i]=new int[matrix[i].size()];
            memset(&(matrix_label[i][0]),0,sizeof(int)*matrix[i].size());
        }

        for(int i=0;i<matrix.size();++i)
        {
            for(int j=0;j<matrix[i].size();++j)
            {
                int len=search(matrix,matrix_label,i,j);
                if(len>max)
                {
                    max=len;
                }
            }
        }
        for(int i=0;i<matrix.size();++i)
        {
            delete[] matrix_label[i];
        }
        delete[] matrix_label;
        return max;
    }
};